class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 创建根节点
const root = new TreeNode("A");

// 创建第二层节点
root.left = new TreeNode("B");
root.right = new TreeNode("C");

// 创建第三层节点
root.left.left = new TreeNode("D");
root.left.right = new TreeNode("E");
root.right.left = new TreeNode("F");
root.right.right = new TreeNode("G");

// 创建第四层节点
root.left.left.left = new TreeNode("H");
root.left.left.right = new TreeNode("I");
/*
 *        A
 *      /   \
 *     B     C
 *    / \   / \
 *   D   E F   G
 *  / \
 * H   I
 */
// function printTree(node, prefix = "", isLeft = false) {
//     if (node === null) return;
//     console.log(prefix + (isLeft ? "├── " : "└── ") + node.value);
//     printTree(node.left, prefix + (isLeft ? "│   " : "    "), true);
//     printTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
// }
//
// printTree(root);
//前序遍历
function preOrder(root){
    if(root===null) return;
    console.log(root.value);
    preOrder(root.left)
    preOrder(root.right)
}
// preOrder(root)

//中序遍历
function inOrder(node){
    if (node===null) return;
    //遍历左子树
    inOrder(node.left)
    console.log(node.value);
    //再遍历右子树
    inOrder(node.right)
}
// inOrder(root)

//后序遍历
function postOrder(node){
    if (node===null) return;
    //遍历左子树
    postOrder(node.left)
    //再遍历右子树
    postOrder(node.right)
    console.log(node.value);

}
// postOrder(root)


//层序遍历
function levelOrder(root){
    if(root===null) return;
    const queue=[]
    queue.push(root)
    while (queue.length>0){
        const node=queue.shift() //从队列里拿到放入的节点
        console.log(node.value);
        //把左右子节点入队
        if(node.left !==null) queue.push(node.left)
        if(node.right !==null) queue.push(node.right)
    }
}
levelOrder(root)



